# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        self.l = len(data)
        if self.l==0:
            return 0
        a =self.first(data,k,0,self.l-1)
        b = self.end(data,k,0,self.l-1)
        if b>-1 and a>-1:
            return b-a+1
        else:
            return 0
    def first(self,data,k,s,e):
        if s>e:
            return -1
        mid = (e+s)//2
        val = data[mid]
        if k==val:
            if (mid>0 and data[mid-1]!=k) or mid==0:
                return mid
            else:
                e = mid-1
        elif k>val:
            s = mid+1
        else:
            e = mid-1
        return self.first(data,k,s,e)
    def end(self,data,k,s,e):
        if s>e:
            return -1
        mid = (e+s)//2
        val = data[mid]
        if k==val:
            if (mid<self.l-1 and data[mid+1]!=k) or mid==self.l-1:
                return mid
            else:
                s = mid+1
        elif k>val:
            s = mid+1
        else:
            e = mid-1
        return self.end(data,k,s,e)

alist = [1,3,3,3,3,4,5]
s = Solution()
print(s.GetNumberOfK(alist, 6))